package com.gwcloud.leetcode.tags.backtrace;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/** 
* @ClassName   : Leetcode047 
* @author      : ganwei 
* @date        : 2020年5月8日 
* @Description : Leetcode047 全排列 II 
*/
public class Leetcode0047 {
	List<List<Integer>> result = new ArrayList<>();
	/**
     * -解题思路，回溯
     */
	public List<List<Integer>> permuteUnique(int[] nums) {
		if(nums.length <= 0) {
			return result;
		}
		Arrays.sort(nums);
		backtrack(nums,new ArrayList<Integer>(),new boolean[nums.length]);
    	return result;
    }
    
	/**
	 * -回溯主体
	 */
	public void backtrack(int[] nums, List<Integer> li,boolean[] isVisited) {
		if(li.size() == nums.length) {
			result.add(new ArrayList<>(li));
			return;
		}
		
		for(int i = 0; i < nums.length; i++) {
			if(isVisited[i]) {
				continue;
			}
			if(i > 0 && nums[i-1] == nums[i] && isVisited[i-1]) {
				continue;
			}
			
			
			li.add(nums[i]);
			isVisited[i] = true;
			
			backtrack(nums,li,isVisited);
			
			li.remove(li.size()-1);
			isVisited[i] = false;
			
		}
		
		
	}
	
	/**
	 * -主函数
	 */
    public static void main(String[] args) {
    	int[] nums = {1,1,1,2};
    	Leetcode0047 l047 = new Leetcode0047();
    	l047.permuteUnique(nums);
    	for(List<Integer> l : l047.result) {
    		for(Integer i : l) {
    			System.out.print(i);
    		}
    		System.out.println();
    	}
    }
}
